\section{M\'odulo Diccionario Arreglo}

\setlength{\parindent}{0pt}

\begin{Interfaz}

\noindent
\textbf{Usa}: Cliente, Nat, Bool, Arreglo, Lista, Titulo\\
\textbf{Se explica con}: \tadNombre{DICCIONARIO}\\
\textbf{G\'eneros}: \TipoVariable{dicc\_a}\\
\textbf{Operaciones}:\\
A modo de simplicidad llamamos $sig$ a tupla(dicc\_t(titulo,nat),nat).\\
\InterfazFuncion{NuevoD}{\In{cls}{lista(tupla(cliente,sig)))}}{dicc\_a(cliente,sig)}
[True]
{$res \igobs$ nuevoD(cls)}
[O($\# scl^2$)]
[Genera un diccionario con las definiciones $cls$.]
	
\InterfazFuncion{Def?}{\In{d}{dicc\_a(cliente,sig))}, \In{c}{cliente}}{bool}
[True]
{$res \igobs$ def$?$(d, c)}
[O($log(\# Claves(d))$)]
[Devuelve true si y solo c esta definido en el diccionario.]

%~ #CLAVES(in d : dicc_a(Cliente,conj_trie(<titulo,nat>))) -> res : nat
	%~ Pre = {true}
	%~ Post = {res =obs #claves(d)}
	%~ Complejidad: O(1)
	%~ Descripción: devuelve la cantidad de claves del diccionario.

\InterfazFuncion{Obtener}{\In{d}{dicc\_a(cliente,sig))}, \In{c}{cliente}}{sig)}
[def$?$(d, c)]
{$res \igobs$ obtener(d, c)}
[O($log(\# Claves(d))$)]
[Devuelve true si y solo c esta definido en el diccionario.]
[$res$ se devuelve por referencia.]

%~ \InterfazFuncion{\#CLAVES}{\In{d}{dicc\_a(cliente,dicc\_t(titulo,nat))}}{nat}
%~ [True]
%~ {$res \igobs$ def$?$(d, c)}
%~ [O($log(\# Claves(d))$)]
%~ [Devuelve true si y solo c esta definido en el diccionario.]

%~ \InterfazFuncion{REDEFINIR}{\Inout{d}{dicc\_a(cliente,dicc\_t(titulo,nat))}, \In{c}{cliente}}{}
%~ [True]
%~ {$res \igobs$ def$?$(d, c)}
%~ [O($log(\# Claves(d))$)]
%~ [Devuelve true si y solo c esta definido en el diccionario.]


\end{Interfaz}

\begin{Representacion}
  
  \Titulo{Representaci\'on de Diccionario Arreglo}

  \begin{Estructura}{dicc\_a}[str]
	donde \textbf{str} es arreglo\_dimensionable de tupla(cliente,sig)\\

    \end{Estructura}

  \Rep[str][e]{[($\forall$i,j: nat)(i < j $\land$ i$\le$tamanio(e) $\land$ j$\le$tamanio(e) $\Rightarrow$ e[i].cliente < e[j].cliente)]}
 
  \AbsFc[str]{diccionario}[e]{d: diccionario $| ((\forall c: cliente) def?(c, d) = esta \Pi_{1} ?(c, e) $ $\land_{L}$ \\ 
  $(\forall c: cliente) def?(c, d) \Rightarrow obtener(c,d) = buscar \Pi_{2}De(c, e) )$ }
 
\textbf{Auxiliares}:

  \tadOperacion{$esta \Pi_{1} ?$}{cliente/c,arreglo\_dimensionable(tupla(cliente,sig))/d}{bool}{}
  \tadAxioma{$esta \Pi_{1} ?$($c$,$d$)}{aux$Esta \Pi_{1} ?$(c,d,0)}
  \tadOperacion{aux$Esta \Pi_{1} ?$}{cliente/c,arreglo\_dimensionable(tupla(cliente,sig))/d, nat/n}{bool}{ n < tamanio(d)}
  \tadAxioma{aux$Esta \Pi_{1} ?$($c$,$d$,$i$)}{\IF i $\ge$ tamanio(e) THEN $False$ ELSE {\IF $\Pi_{1}$(e[i]) = c THEN $True$ 
  ELSE aux$Esta \Pi_{1} ?$($c$,$d$,$i+1$) FI}FI}
  
  \tadOperacion{$buscar \Pi_{2}De$}{cliente/c,arreglo\_dimensionable(tupla(cliente,sig))/d}{sig}{$esta \Pi_{1} ?$(c,d)}
  \tadAxioma{$buscar \Pi_{2}De$($c$,$d$)}{aux$buscar \Pi_{2}De$(c,d,0)}
  \tadOperacion{aux$buscar \Pi_{2}De$}{cliente/c,arreglo\_dimensionable(tupla(cliente,sig))/d, nat/n}{bool}{ n < tamanio(d)}
  \tadAxioma{aux$buscar \Pi_{2}De$($c$,$d$,$i$)}{\IF $\Pi_{1}$(e[i]) = c THEN $\Pi_{2}$(e[i])
  ELSE aux$buscar \Pi_{2}De$($c$,$d$,$i+1$) FI}
  
\end{Representacion}
\begin{Algoritmos}

  
\begin{lstlisting}
iNuevoD(in scl : lista(tupla(cliente,sig)) -> res : str {
	

	var arregloAux: arreglo_dimensionable

	arregloAux <- CrearArreglo(Longitud(scl)) // O(1)

	var listaClientes: itLista 
	listaClientes <- CrearIt(scl)


	var i: nat
	
	i <- 0

	while (HaySiguiente(listaClientes)) // O(n)
		
		arregloAux[i] = Pi_1(Siguiente(listaClientes))
		
		i <- i+1

		Avanzar(listaClientes)
	
	end while

	SelectionSort(arregloAux) // O(n^2)
		
	listaClientes <- CrearIt(scl) // O(1)

	res <- CrearArreglo(Longitud(scl)) // O(1)

	i<-0

	while (i <- Tamanio(arregloAux)) // O(n^2)
		
		
		while (HaySiguiente(listaClientes))

			if arregloAux[i] = Pi_1(Siguiente(listaClientes)) then
				
				res[i] = Siguiente(listaClientes)

				end while

			end if

			Avanzar(listaClientes)

		end while

		i <- i + 1

	end while
}

\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($\# lista(tupla(cliente,sig))^2$)\\
\end{Descripcionbis}

\begin{lstlisting}
iDef?(in d : str, in c : cliente) -> res : bool {

	var med :int
	var max: int
	var min: int

	max <- Tamanio(d)
	min <- 0

	while (max >= min) // O(log(Tamanio(d)))
	
		med <- (max - min) / 2
		
		if d[med] = c then

			res <- true

		else
			if d[med] < c then
				
			 	min <- med + 1
			
			else

				max <- med - 1

			end if

		end if

	end while
	
}

\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($log(Tamanio(d))$)\\
\end{Descripcionbis}

\begin{lstlisting}
iObtener(in d : str, in c : Cliente) -> res :sig {

	var med :int
	var max: int
	var min: int
	var pos: int

	max <- Tamanio(d)
	min <- 0

	while (max >= min) // log(Tamanio(d))
	
		med <- (max - min) / 2
		
		if d[med] = c then

			pos <- c

		else
			if d[med] < c then
				
			 	min <- med + 1
			
			else

				max <- med - 1

			end if

		end if

	end while

	res <- Pi_2(d[pos])
	
}

\end{lstlisting}
\begin{Descripcionbis}
COMPLEJIDAD TEMPORAL: O($log(Tamanio(d))$)\\
\end{Descripcionbis}

\end{Algoritmos}
